package leetcode.code1703;

import java.util.LinkedList;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public int minMoves(int[] nums, int k) {
		if (k == 1) {
			return 0;
		}
		int len = nums.length;
		int[] lstack = new int[len];// 左栈
		int pl = 0;// 左栈顶
		int[] rstack = new int[len];// 右栈
		int prd = 0;// 右栈底
		int pr = 0;// 右栈顶
		for (int i = 0; i < len; i++) {
			if (nums[i] == 1) {
				rstack[prd++] = i;
			}
		}
		LinkedList<Integer> zeros = new LinkedList<>();
		int ans = Integer.MAX_VALUE;
		// [0,1,0,0,1,1,0,1,0,1,1,1,1,0,1,0]
		// [1,0,0,1,0,0,1,0,1,1]
		// [1,0,0,1,0,0,1,0,1,1]
		//    0 3 4 5 - 7 8 9
		for (int i = 0; i < len; i++) {
			int in = nums[i];
			if (in == 1) {
				pr++;
			} else {
				zeros.add(i);
			}
			int out = i - k;
			if (out >= 0) {
				if (nums[out] == 1) {
					lstack[pl++] = out;
				} else {
					zeros.poll();
				}
			}
			if (i >= k - 1) {
				ans = Math.min(ans, this.f(lstack, pl, rstack, pr, prd, zeros));
			}
		}
		return ans;
	}

	private int f(int[] lstack, int pl, int[] rstack, int pr, int prd, LinkedList<Integer> zeros) {
		LinkedList<Integer> tmp = new LinkedList<>(zeros);
		int size = zeros.size();
		int ans = 0;
		while (size > 0) {
			int mid = tmp.size() >> 1;
			Integer zero = zeros.get(mid);
			int dis1 = pl > 0 ? Math.abs(zero - lstack[pl - 1]) : Integer.MAX_VALUE;
			int dis2 = pr < prd ? Math.abs(zero - rstack[pr]) : Integer.MAX_VALUE;
			if (dis1 < dis2) {
				ans += dis1;
				pl--;
			} else {
				ans += dis2;
				pr++;
			}
			tmp.remove(mid);
			size--;
		}
		return ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(6, this.minMoves(HelpDebug.str2array3("[1,0,0,1,1,0,0,0,0,1]"), 4));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub
		HelpDebug.compare(8, this.minMoves(HelpDebug.str2array3("[1,1,0,0,1,0,0,0,0,1]"), 4));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

		HelpDebug.compare(8, this.minMoves(HelpDebug.str2array3("[1,1,0,0,1,0,1,0,0,1]"), 5));
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub
		HelpDebug.compare(10, this.minMoves(HelpDebug.str2array3("[1,1,0,0,0,0,0,1,1,1]"), 5));

	}

	public void debug5() {
		// TODO Auto-generated method stub
		HelpDebug.compare(8, this.minMoves(HelpDebug.str2array3("[1,0,0,1,0,0,1,0,1,1]"), 5));

	}

	public void debug6() {
		// TODO Auto-generated method stub
		HelpDebug.compare(0, this.minMoves(HelpDebug.str2array3("[1,1]"), 1));

	}

	public void debug7() {
		// TODO Auto-generated method stub
		HelpDebug.compare(1, this.minMoves(HelpDebug.str2array3("[1,0,1,1,1,1,1,1,1,1,1,1,1,1,1]"), 14));

	}

	public void debug8() {
		// TODO Auto-generated method stub
		HelpDebug.compare(4, this.minMoves(HelpDebug.str2array3("[0,1,0,0,1,1,0,1,0,1,1,1,1,0,1,0]"), 7));

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug5();
		so.debug7();
		so.debug6();
		so.debug8();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
